package main

import "fmt"

// 假设你是一个旅行者，背包的最大承重量为 W。现在有一系列物品，每件物品都有自己的重量和价值。
// 你的目标是在不超过背包承重的情况下，尽可能装入更多总价值的物品。请设计一个算法，找出最佳的装包方案。
//
// 注意：每种物品只有一件，要么装入背包，要么不装入。
//
// 你可以按照以下要求对此问题进行思考和解答：
//
// 定义物品的重量和价值；
// 确定背包的承重量 W；
// 列举几个具体的物品重量和价值；
// 提出一个算法或思路，解决如何选择装入背包的物品，使得总价值最大。
// 如果当前物品重量大于背包的承受量,那么总价值就是上一行同一列的值,
// 如果当前物品重量不大于背包的承受量,那么分两种情况:第一:不放入本物品,总价值也是上一行同一列的值
// 第二放入本物品,

func knapsack(weights, values []int, W int) int {
	n := len(weights) // 物品数量
	dp := make([][]int, n+1)

	// 初始化dp数组
	for i := range dp {
		dp[i] = make([]int, W+1)
	}

	// 填充dp数组
	for i := 1; i <= n; i++ {
		for w := 1; w <= W; w++ {
			if w >= weights[i-1] {
				// 选择当前物品或不选择当前物品，取价值较大的一个
				dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
			} else {
				// 背包容量不足以放下当前物品，不选择当前物品
				dp[i][w] = dp[i-1][w]
			}
		}
	}

	// 返回结果
	return dp[n][W]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	weights := []int{2, 3, 4} // 物品重量
	values := []int{3, 4, 5}  // 物品价值
	W := 5                    // 背包最大容量

	fmt.Println("最大价值为:", knapsack(weights, values, W))
}
